package day230520;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/20 22:30
 * 左右最值的最大差
 */
public class MaxGap {

    public int findMaxGap(int[] A, int n) {
        // 假设划分的位置为 k
        // 左侧数组的范围为 [0, k], 右侧数组的范围为 [k+1, n-1];
        // 无论 k 的取值如何, 左侧数组必包含 0 位置, 右侧数组必包含 n-1 位置
        // 求左部分的最大值与右部分的最大值差值的绝对值的最大值, 即尽可能让左侧大, 右侧尽可能小
        // 先找到最大值
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            maxValue = Math.max(A[i], maxValue);
        }
        // 两种划分可能, 较小的相对大值在左侧或者右侧
        return Math.max(Math.abs(maxValue - A[0]),
                Math.abs(maxValue - A[n-1]));
    }
}
